#include "QuadTree.h"

QuadTree::QuadTree(): m_isLeaf(true)
{	
}

QuadTree::QuadTree( int x,int y, int width, int height ): m_isLeaf(true)
{
	m_rect = Rect(x,y,width,height);
}

QuadTree::QuadTree( sf::Vector2i pos, sf::Vector2i size ): m_isLeaf(true)
{
	m_rect = Rect(pos,size);
}

QuadTree::QuadTree( const Rect& rect )
{
	m_rect = rect;
}

QuadTree::~QuadTree()
{

}

void QuadTree::Subdivide( int level )
{
	if(level < 1) return;
	for(uint16 i=0; i<level; i++) {
		Subdivide();
	}
}

void QuadTree::Subdivide()
{
	if(m_isLeaf) {
		int childWidth  = m_rect.w >> 1; //sneaky way to divide by 2
		int childHeight = m_rect.h >> 1; 
		//divide the parent into 4 smaller parts
		m_children.push_back(QuadTree(m_rect.x, m_rect.y, childWidth, childHeight));
		m_children.push_back(QuadTree(m_rect.x+childWidth, m_rect.y,childWidth, childHeight));
		m_children.push_back(QuadTree(m_rect.x+childWidth, m_rect.y+childHeight, childWidth,childHeight));
		m_children.push_back(QuadTree(m_rect.x, m_rect.y+childHeight,childWidth,childHeight));
		
		m_isLeaf = false;	//you are no longer a leaf
	} else {
		for(uint16 i = 0; i < 4; i++) {
			m_children[i].Subdivide();
		}
	}
}

void QuadTree::FindEntitiesInArea( const Rect& area, EntityList& entities )
{
	if(!IsCollision(m_rect,area)) return;
	
	if(m_isLeaf) {
		if(m_entities.size())
			entities.insert(entities.end(),m_entities.begin(),m_entities.end());
	} else {
		for(uint16 i=0; i<4; i++) 
			m_children[i].FindEntitiesInArea(area,entities);
	}
}

void QuadTree::Insert( Entity* entity )
{
	if(!entity) return;

	if(m_isLeaf) {
		EntityList::iterator it = std::find(m_entities.begin(),m_entities.end(),entity);
		if(it == m_entities.end() && IsCollision(m_rect,entity->GetRect())) {
			m_entities.push_back(entity);
		}
	} else {
		for(uint16 i=0; i<4; i++) {
			m_children[i].Insert(entity);
		}
	}
}

void QuadTree::Delete( Entity* entity )
{
	if(m_isLeaf) {
		EntityList::iterator it = std::find(m_entities.begin(), m_entities.end(),entity);
		if(it != m_entities.end()) {
			m_entities.erase(it);
		}
	} else {
		for(uint16 i=0; i<4; i++) {
			m_children[i].Delete(entity);
		}
	}
}

void QuadTree::FindNearbyEntities( Entity* entity, EntityList& neighbours )
{
	if(m_isLeaf) {
		if(IsCollision(m_rect,entity->GetRect())) {
			for(uint16 i=0; i<4; i++) {
				neighbours.insert(neighbours.end(), m_entities.begin(),m_entities.end());
			}
		}
	} else {
		m_children[0].FindNearbyEntities(entity, neighbours);
		m_children[1].FindNearbyEntities(entity, neighbours);
		m_children[2].FindNearbyEntities(entity, neighbours);
		m_children[3].FindNearbyEntities(entity, neighbours);
	}
}